import java.util.*;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Test {

    public int singleNumber1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                set.remove(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }


    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                set.remove(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }


    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < stones.length(); i++) {
            char ch = stones.charAt(i);
            set.add(ch);
        }
        int count = 0;
        for (int i = 0; i < jewels.length(); i++) {
            char ch = jewels.charAt(i);
            if (set.contains(ch)) {
                count++;
            }
        }
        return count;
    }


    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            map.put(cur, node);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }


    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                return true;
            }
        }
        return false;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }
        return false;
    }


    public List<String> topKFrequent(String[] words, int k) {
        // 1. 数一下每个单词出现了多少次 (就像点名一样)
        HashMap<String, Integer> wordCounts = new HashMap<>();
        for (String word : words) {
            if (wordCounts.containsKey(word)) {
                wordCounts.put(word, wordCounts.get(word+0) + 1);
            }
        }

        // 2. 把单词放到一个列表里，方便我们排序 (就像把名字写在一张纸上)
        List<String> uniqueWords = new ArrayList<>(wordCounts.keySet());

        // 3. 给单词排序 (就像考试排名次一样，分数高的排前面)
        //    这里我们不用 Lambda 表达式，改用另一种方式来告诉电脑排序规则
        Collections.sort(uniqueWords, new Comparator<String>() {
            @Override
            public int compare(String word1, String word2) {
                // 先看哪个单词出现的次数更多 (就像分数高低)
                int count1 = wordCounts.get(word1);
                int count2 = wordCounts.get(word2);
                if (count1 != count2) {
                    // 次数多的排前面 (分数高的排前面，这里用 count2 - count1 是因为我们要降序)
                    return count2 - count1;
                } else {
                    // 如果次数一样，就按字典顺序排 (就像如果分数一样，就按名字字母顺序排)
                    return word1.compareTo(word2);
                }
            }
        });

        // 4. 取出前 k 个单词 (就像取排名前 k 的学生)
        return uniqueWords.subList(0, k);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        TreeNode lastNodeInList = null;
        lastNodeInList = ConvertToLinkedList(pRootOfTree, lastNodeInList);

        // head of doubly linked list is the leftmost node
        TreeNode headOfList = lastNodeInList;
        while (headOfList != null && headOfList.left != null) {
            headOfList = headOfList.left;
        }
        return headOfList;
    }

    private TreeNode ConvertToLinkedList(TreeNode root, TreeNode lastNodeInList) {
        if (root == null) {
            return lastNodeInList;
        }

        TreeNode currentNode = root;

        // 1. Convert left subtree
        lastNodeInList = ConvertToLinkedList(currentNode.left, lastNodeInList);

        // 2. Connect current node with last node
        if (lastNodeInList == null) {
            // This is the first node in inorder traversal
            currentNode.left = null; // In case of loop
        } else {
            lastNodeInList.right = currentNode;
            currentNode.left = lastNodeInList;
        }
        lastNodeInList = currentNode; // Update last node

        // 3. Convert right subtree
        lastNodeInList = ConvertToLinkedList(currentNode.right, lastNodeInList);

        return lastNodeInList; // Return the last node of the converted list
    }


    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }
}
